#include "Verifier_Two_Stage.h"

Verifier_Two_Stage::Verifier_Two_Stage(double min_ratio,
                                       Cluster_Metric metric,
                                       Splitter& splitter) {
    LOG_ENTER(FIX, "Verifier_Two_Stage::Verifier_Two_Stage");
    LOG(FIX) << "min_ratio=" << min_ratio;

    min_good_split_ratio = min_ratio;
    cluster_metric = metric;
    cluster_splitter = splitter;

    LOG_EXIT();
}

vector<Tree_Of_Clusters *>
*Verifier_Two_Stage::verify(vector<Cluster*>& children) {

    Cluster *S1,*S2;
    Cluster *a,*b,*c,*d;

    S1 = children[0];
    S2 = children[1];

    if (S1->span.n == 1 && S2->span.n == 1) {
        // we got down to single items.  Skip to end of loop.
        return make_subtrees(S1, S2);
    }

    else if (S1->span.n == 1) {
        // S1 too small. Split S2, and check if good split.
        cluster_splitter->split(S2, a,b);

        Bad_Split::Type fixup_code = check(S1,a,b);

        if (fixup_code != Bad_Split::OK) {
            // re-shape S1 and S2 by moving one of a,b over to S1.
            fix(fixup_code, S1,S2, a,b);
            return make_subtrees(S1, S2);
        }
    }
    else if (S2->span.n == 1) { // S2 too small.
        cluster_splitter->split(S1,a,b);

        Bad_Split::Type fixup_code = fixer->check(S2,a,b);

        if (fixup_code != Bad_Split::OK) {
            // re-shape S1 and S2 by moving one of a,b over to S2.
            fix(fixup_code, S2,S1, a,b);
            return make_subtrees(S1, S2);
        }
    }
    else {
        //
        // General case.  Check for bad splits.
        //
        cluster_splitter->split(S1, a,b);
        cluster_splitter->split(S2, c,d);

        Bad_Split::Type fixup_code = check(a,b,c,d);

        if (fixup_code != Bad_Split::OK) {
            // re-shape S1 and S2 by moving one of a,b,c,d around.
            fix(fixup_code, S1,S2, a,b,c,d);
            return make_subtrees(S1, S2);
        }
        else {
            //
            // split was OK.  Record the subclusters into the subtrees
            //
            vector<Tree_Of_Clusters *> *subtrees = make_subtrees(S1, S2);

            CT_Node *root = subtrees->at(0)->root;
            subtrees->at(0).set_children(root, a,b);

            root = subtrees->at(1)->root;
            subtrees->at(1).set_children(root, c,d);
            return subtrees;
        }
    }
}

//
// Check if a split was bad.
// a and b are children of one cluster, while c and d are children of another.
// If the initial split was good, then a and b should be far from c and d.
// If not, then maybe (a,c) or (a,d) or (b,c) or (b,d) belong together.
// This method detects that problem.  The "fix" method corrects the problem
// by merging one of the 4 clusters into the other pair.
//
Bad_Split::Type Verifier_Two_Stage::check(Cluster *a, Cluster *b,
                                          Cluster *c, Cluster *d) {
    LOG_ENTER(FIX, "Verifier_Two_Stage::check(a,b,c,d)");

    LOG(FIX) << "cluster a:";
    a->span.write_IDs(Log::output); Log::output << "\n";
    LOG(FIX) << "cluster b:";
    b->span.write_IDs(Log::output); Log::output << "\n";
    LOG(FIX) << "cluster c:";
    c->span.write_IDs(Log::output); Log::output << "\n";
    LOG(FIX) << "cluster d:";
    d->span.write_IDs(Log::output); Log::output << "\n";
    Log::output.flush();

    double dist_ab = cluster_metric.distance(a,b);
    double dist_ac = cluster_metric.distance(a,c);
    double dist_ad = cluster_metric.distance(a,d);
    double dist_bc = cluster_metric.distance(b,c);
    double dist_bd = cluster_metric.distance(b,d);
    double dist_cd = cluster_metric.distance(c,d);

    LOG(FIX) << "dist_ab=" << dist_ab;
    LOG(FIX) << "dist_ac=" << dist_ac;
    LOG(FIX) << "dist_ad=" << dist_ad;
    LOG(FIX) << "dist_bc=" << dist_bc;
    LOG(FIX) << "dist_bd=" << dist_bd;
    LOG(FIX) << "dist_cd=" << dist_cd;

    LOG(FIX) << "dist_ac/dist_ab=" << dist_ac/dist_ab;
    LOG(FIX) << "dist_ac/dist_cd=" << dist_ac/dist_cd;
    LOG(FIX) << "dist_ad/dist_ab=" << dist_ad/dist_ab;
    LOG(FIX) << "dist_ad/dist_cd=" << dist_ad/dist_cd;
    LOG(FIX) << "dist_bc/dist_ab=" << dist_bc/dist_ab;
    LOG(FIX) << "dist_bc/dist_cd=" << dist_bc/dist_cd;
    LOG(FIX) << "dist_bd/dist_ab=" << dist_bd/dist_ab;
    LOG(FIX) << "dist_bd/dist_cd=" << dist_bd/dist_cd;
    LOG(FIX) << "min ratio=" << min_good_split_ratio;

    //
    // How do we know that, for instance, c belongs with (a b), and not
    // with its current sibling d?  Well, c could be a lot closer to a than
    // it is to d.  Also, c could be a lot closer to b than it is to d.
    // In other words,
    //  min(d(a,c)/d(c,d) , d(b,c)/d(c,d)) < min good split ratio.
    //

    Bad_Split::Type result;

    if (dist_ab == 0.0 || dist_cd == 0.0) {
        result = Bad_Split::OK; // degenerate data. do nothing.
    }

    if (std::min(dist_ac/dist_cd, dist_bc/dist_cd) < min_good_split_ratio) {
        result = Bad_Split::MOVE_C_TO_AB;
    }

    else if (std::min(dist_ad/dist_cd, dist_bd/dist_cd) < min_good_split_ratio) {
        result = Bad_Split::MOVE_D_TO_AB;
    }

    else if (std::min(dist_ac/dist_ab, dist_ad/dist_ab) < min_good_split_ratio) {
        result = Bad_Split::MOVE_A_TO_CD;
    }

    else if (std::min(dist_bc/dist_ab, dist_bd/dist_ab) < min_good_split_ratio) {
        result = Bad_Split::MOVE_B_TO_CD;
    }

    else {
        result = Bad_Split::OK;
    }

    LOG(FIX) << "result=" << result;
    LOG_EXIT();

    return result;
}

//
// Another check if a split was bad.
// Special case: S is a single item, a, b were split from another cluster.
// We're checking whether a or b belongs with S, and not with each other.
// See comments on check above for details.
//
Bad_Split::Type Verifier_Two_Stage::check(Cluster *S, Cluster *a, Cluster *b) {
    LOG_ENTER(FIX, "Verifier_Two_Stage::check(S,a,b)");

    LOG(FIX) << "cluster S:";
    S->span.write_IDs(Log::output); Log::output << "\n";
    LOG(FIX) << "cluster a:";
    a->span.write_IDs(Log::output); Log::output << "\n";
    LOG(FIX) << "cluster b:";
    b->span.write_IDs(Log::output); Log::output << "\n";

    double dist_Sa = cluster_metric.distance(S,a);
    double dist_Sb = cluster_metric.distance(S,b);
    double dist_ab = cluster_metric.distance(a,b);

    LOG(FIX) << "dist_Sa=" << dist_Sa;
    LOG(FIX) << "dist_Sb=" << dist_Sb;
    LOG(FIX) << "dist_ab=" << dist_ab;
    if (dist_ab != 0.0) {
        LOG(FIX) << "dist_Sa/dist_ab=" << dist_Sa/dist_ab;
        LOG(FIX) << "dist_Sb/dist_ab=" << dist_Sa/dist_ab;
    }

    Bad_Split::Type result;

    if (dist_ab == 0.0) {
        result = Bad_Split::OK; // degenerate data. do nothing.
    }

    if (dist_Sa/dist_ab < min_good_split_ratio) {
        result = Bad_Split::MOVE_A_TO_S;
    }

    else if (dist_Sb/dist_ab < min_good_split_ratio) {
        result = Bad_Split::MOVE_B_TO_S;
    }

    else {
        result = Bad_Split::OK;
    }

    LOG(FIX) << "result=" << result;
    LOG_EXIT();

    return result;
}

//
// Fix a bad split, by moving a subset over, next to another pair of subsets.
// Coming in, S1 has children a,b, and S2 has children c,d.
//

void Verifier_Two_Stage::fix(Bad_Split::Type bad_split_type,
                             Cluster*& S1, Cluster*& S2,
                             Cluster *a, Cluster *b, Cluster *c, Cluster *d) {
    LOG_ENTER(FIX, "Verifier_Two_Stage::fix(S1,S2,a,b,c,d)");
    LOG(FIX) << "split_type=" << bad_split_type;

    delete_stale_clusters();

    switch(bad_split_type) {
    case Bad_Split::MOVE_C_TO_AB:
        S1->append(c);

        // d is now lone child of S2, promote it, and kill
        // other nodes (no longer needed)
        is_stale(S2);
        is_stale(a);
        is_stale(b);
        is_stale(c);

        S2 = d;

        break;

    case Bad_Split::MOVE_D_TO_AB:
        S1->append(d);

        // now c is lone child of S2, promote it, and kill
        // other nodes (no longer needed)
        is_stale(S2);
        is_stale(a);
        is_stale(b);
        is_stale(d);

        S2 = c;

        break;

    case Bad_Split::MOVE_A_TO_CD:
        S2->append(a);

        // now b is lone child of S1. promote it, and kill
        // other nodes (no longer needed)
        is_stale(S1);
        is_stale(a);
        is_stale(c);
        is_stale(d);

        S1 = b;

        break;

    case Bad_Split::MOVE_B_TO_CD:
        S2->append(b);

        // now a is lone child of S1. promote it, and kill
        // other nodes (no longer needed)
        is_stale(S1);
        is_stale(b);
        is_stale(c);
        is_stale(d);

        S1 = a;

        break;
    }

    LOG(FIX) << "After fix(S1,S2,a,b,c,d), reconfigured S1 and S2 are:";
    LOG(FIX) << "cluster S1, ID " << S1->ID << ":";
    S1->span.write_IDs(Log::output); Log::output << "\n";
    LOG(FIX) << "cluster S2, ID " << S2->ID << ":";
    S2->span.write_IDs(Log::output); Log::output << "\n";

    delete_stale_clusters();

    LOG_EXIT();
}

//
// 3-subset version of fixBadSplit.
//
void Verifier_Two_Stage::fix(Bad_Split::Type bad_split_type,
                             Cluster *S, Cluster*& ab,
                             Cluster *a, Cluster *b) {
    LOG_ENTER(FIX, "Verifier_Two_Stage::fix(S,ab,a,b)");
    LOG(FIX) << "split_type=" << bad_split_type;

    switch(bad_split_type) {
    case Bad_Split::MOVE_A_TO_S:
        S->append(a);

        // now b is lone child of ab. promote it, and kill
        // other nodes (no longer needed)
        is_stale(ab);
        is_stale(a);

        ab = b;

        break;

    case Bad_Split::MOVE_B_TO_S:
        S->append(b);

        // now a is lone child of ab. promote it, and kill
        // other nodes (no longer needed)
        is_stale(ab);
        is_stale(b);

        ab = a;

        break;
    }

    LOG(FIX) << "After fix(S,ab,a,b), reconfigured S is:";
    LOG(FIX) << "cluster S, ID " << S->ID << ":";
    S->span.write_IDs(Log::output); Log::output << "\n";

    delete_stale_clusters();

    LOG_EXIT();
}

void Verifier_Two_Stage::is_stale(Cluster *cluster) {
    LOG_ENTER(FIX, "Verifier_Two_Stage::is_stale");
    LOG(FIX) << " cluster (ID=" << cluster->ID << ") is stale";

    stale_clusters.push_back(cluster);

    LOG_EXIT();
}

void Verifier_Two_Stage::delete_stale_clusters() {
    LOG_ENTER(FIX, "Verifier_Two_Stage::delete_stale_clusters");
    LOG(FIX) << "there are " << stale_clusters.size() << " stale clusters";

    for (std::vector<Cluster*>::iterator iter = stale_clusters.begin();
         iter != stale_clusters.end();
         iter++) {

        LOG(FIX) << " deleting stale cluster (ID=" << (*iter)->ID << ")";

        delete *iter;
    }
    stale_clusters.clear();

    LOG_EXIT();
}


